而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。

冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相 邻元素时，交换它们的位置;当一个元素小于或等于右侧相邻元素时，位置不变。 详细过程如下。

有 8 个数字组成一个无序数列{5,8,6,3,9,2,1,7}，希望按照从小到大的顺序 对其进行排序。

冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序
算法的每一轮都要遍历所有元素，总共遍历(元素数量-1)轮，所以平均时间复杂 度是 O(n2)。

```js
// 演示
let arr = [1, 3, 5, 2, 6, 7, 8, 9];
for (let k = 0; k < arr.length - 1; k++) {
  //有序标记，每一轮的初始值都是true
  for (let i = 0; i < arr.length - 1 - i; i++) {
    if (arr[i] > arr[i + 1]) {
      let start = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = start;
    }
  }
}
console.log(arr, count);
```

上面一共会经历 8 轮，在第 4 轮时都已经排序完成了，但是后面 4 轮还是会循环。来优化一下。

- 优点 1 (如果排序已完成，后面循环终止)

```js
// 演示
let arr = [1, 3, 5, 2, 6, 7, 8, 9];

for (let k = 0; k < arr.length - 1; k++) {
  //有序标记，每一轮的初始值都是true
  let isSorted = true;
  for (let i = 0; i < arr.length - 1 - k; i++) {
    if (arr[i] > arr[i + 1]) {
      let start = arr[i];
      arr[i] = arr[i + 1];
      arr[i + 1] = start;
      isSorted = false;
    }
  }
  if (isSorted) break;
}
console.log(arr);
```

还有一个问题 3,4,2,1,5,6,7,8 后面的 5，6，7，8， 每次都要进行比较。那怎么优化呢?

```js

 let arr = [1, 3, 5, 2, 6, 7, 8, 9];
      let sortBorder = arr.length - 1;
      let lastExchangeIndex = 0; // 记录最后一次交换的位置
      let count = 1;
      for (let k = 0; k < arr.length - 1; k++) {
        //有序标记，每一轮的初始值都是true
        let isSorted = true;
        for (let i = 0; i < sortBorder; i++) {
          if (arr[i] > arr[i + 1]) {
            let start = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = start;
            isSorted = false;
            // 更新为最后一次交换元素的位置
            lastExchangeIndex = i;
          }
          count++;
        }
        sortBorder = lastExchangeIndex;
        if (isSorted) break;
      }
      console.log(arr, count);
```


其实这仍然不是最优的，还有一种排序算法叫作鸡尾酒排序，是基于冒泡排序的一种升级排序法。
